__auth__ = "miao.zhifeng<19195659@qq.com>"
__doc__ = """ 
递归—— 斐波那契数列
1. <wikipedia>
费波那契数列，又译费波拿契数、斐波那契数列、斐波那契数列、黄金分割数列。

2. <说明>源于兔子繁殖，羊的繁殖，细胞分裂等问题，
前后项比例逐步接近黄金分割数 0.618， (1+sqrt(5))/2

3. 描述兔子生长的数目时用上了这数列
    第一个月初有一对刚诞生的兔子
    第二个月之后（第三个月初）它们可以生育
    每月每对可生育的兔子会诞生下一对新兔子
    兔子永不死去
  假设在n月有可生育的兔子总共a对，n+1月就总共有b对。
在n+2月必定总共有a+b对： 因为在n+2月的时候，
前一月（n+1月）的b对兔子可以存留至第n+2月（在当月属于新诞生的兔子尚不能生育）。
而新生育出的兔子对数等于所有在n月就已存在的a对
4. 数列的数学表示
  Fib(n)=
         1                 (n=1)
         1                 (n=2)
         Fib(n-1)+Fib(n-2) (n>2)

"""
import math

#使用递归定义Fibonacci数列
# n 表示数列中第n个位置，注意，n从1开始
def Fib(n):
	if n<=1: 
		return 1
	if n==2: 
		return 1
	else:
		return Fib(n-1) + Fib(n-2)

# 使用动态规划法优化递归程序，
# 重复利用已经计算的子结构结果
def fastFib(n,mem):
	if not n in mem.keys():
		mem[n] = fastFib(n-1,mem)+fastFib(n-2,mem)
	return mem[n]
def FibDP(n):
	mem = {0:1,1:1,2:1}
	return fastFib(n,mem)

# 打印出黄金分割比率
golden = (math.sqrt(5)-1)/2
print("黄金比率为={0}".format(golden))

for i in range(1,100):
	item_cur = FibDP(i)
	item_next = FibDP(i+1)
	d = item_cur/item_next
	print("{0:3d}: {1:30d} / {2:30d} = {3}".format(i,item_cur,item_next,d))
